Network routers can be used to forward data packets from a source computing device to a destination computing device in a computer network. In larger networks, a data packet may be routed through multiple routers before reaching its ultimate destination. When one router transmits a data packet to a neighboring router in the network, the transfer can be referred to as a “hop.” When a router receives a data packet and identifies a neighboring router to which the data packet should be transmitted, it can be said to have identified a “next hop” for the data packet. At least some routers are configured to determine next hops for data packets using routing tables. A routing table can be used to determine associations between network address prefixes and next hops to which data packets matching the network address prefixes should be routed. Network routing protocols exist that enable routers to build routing tables and converge on a shared network topology. Example routing protocols include the Border Gateway Protocol (BGP), the Open Shortest Path First protocol (OSPF), and the Intermediate System to Intermediate System protocol (IS-IS).
Previous strategies for converging on a shared network topology include transmitting route advertisements between routers in a fully meshed network, or using a route reflector to reflect route advertisements sent from one router to all other routers connected to the route reflector. In some protocols (such as BGP) each router maintains a routing information base (RIB) where the router stores all received route information in an on-board memory. The router may then use the information in the RIB to generate a routing table that contains a set of selected next hops for various network address prefixes. There is a desire to expedite convergence for any network changes. Large numbers of prefixes can cause convergence delays resulting in slowing of the overall network throughput or even packet loss.